With the improvement of the public transportation infrastructure, an increasing awareness of the environment, and the rising cost of gasoline, many people have begun using various forms of public transportation. Rather than using their own vehicles, people have increasingly used railway transportation, buses, and/or ferries for their travel needs. Because of this increase in use of public transportation, public transit planning systems have been developed. These systems provide users with directions to travel between a starting location to a destination location via various forms of public transportation.
Typically, in these systems, a query including a starting location and a destination is received, and the transit planning systems provide step by step directions to reach the destination using one or more forms of public transportation. For example, the directions can include a sequence of which public transit vehicles (e.g., buses, trains, etc.) are used and which stops at public transit locations need to be made in order to reach the destination of the trip. The directions may include a transfer to another transit vehicle required at the different transit locations along the trip. Thus, the planning systems provide a mechanism that offers information for people to easily plan their trips using public transportation.
Typically, to determine the directions for a trip, these conventional transit planning systems analyze, at query time, various routes between the starting and destination locations of the trip in order to determine the optimal path to reach the destination. This approach is useful when there are a relatively small number of potential routes between the locations due to a limited number of available transit options. However, due to the expansion of the public transportation infrastructure and the ability to transfer between different transportation systems (e.g., transfer between a train and bus at a common station), the number of possible routes between any given starting location and destination location has grown significantly. Thus, the time needed during query time to calculate the optimal path to reach a destination has also increased dramatically thereby increasing the time that users have to wait to receive results.